<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<HTML
><HEAD
><TITLE
>Free Space Map</TITLE
><META
NAME="GENERATOR"
CONTENT="Modular DocBook HTML Stylesheet Version 1.79"><LINK
REV="MADE"
HREF="mailto:pgsql-docs@postgresql.org"><LINK
REL="HOME"
TITLE="PostgreSQL 9.1.2 Documentation"
HREF="index.html"><LINK
REL="UP"
TITLE="Database Physical Storage"
HREF="storage.html"><LINK
REL="PREVIOUS"
TITLE="TOAST"
HREF="storage-toast.html"><LINK
REL="NEXT"
TITLE="Visibility Map"
HREF="storage-vm.html"><LINK
REL="STYLESHEET"
TYPE="text/css"
HREF="stylesheet.css"><META
HTTP-EQUIV="Content-Type"
CONTENT="text/html; charset=ISO-8859-1"><META
NAME="creation"
CONTENT="2011-12-01T22:07:59"></HEAD
><BODY
CLASS="SECT1"
><DIV
CLASS="NAVHEADER"
><TABLE
SUMMARY="Header navigation table"
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
><TR
><TH
COLSPAN="5"
ALIGN="center"
VALIGN="bottom"
><A
HREF="index.html"
>PostgreSQL 9.1.2 Documentation</A
></TH
></TR
><TR
><TD
WIDTH="10%"
ALIGN="left"
VALIGN="top"
><A
TITLE="TOAST"
HREF="storage-toast.html"
ACCESSKEY="P"
>Prev</A
></TD
><TD
WIDTH="10%"
ALIGN="left"
VALIGN="top"
><A
HREF="storage.html"
ACCESSKEY="U"
>Up</A
></TD
><TD
WIDTH="60%"
ALIGN="center"
VALIGN="bottom"
>Chapter 55. Database Physical Storage</TD
><TD
WIDTH="20%"
ALIGN="right"
VALIGN="top"
><A
TITLE="Visibility Map"
HREF="storage-vm.html"
ACCESSKEY="N"
>Next</A
></TD
></TR
></TABLE
><HR
ALIGN="LEFT"
WIDTH="100%"></DIV
><DIV
CLASS="SECT1"
><H1
CLASS="SECT1"
><A
NAME="STORAGE-FSM"
>55.3. Free Space Map</A
></H1
><P
>Each heap and index relation, except for hash indexes, has a Free Space Map
(FSM) to keep track of available space in the relation. It's stored
alongside the main relation data in a separate relation fork, named after the
filenode number of the relation, plus a <TT
CLASS="LITERAL"
>_fsm</TT
> suffix. For example,
if the filenode of a relation is 12345, the FSM is stored in a file called
<TT
CLASS="FILENAME"
>12345_fsm</TT
>, in the same directory as the main relation file.</P
><P
>The Free Space Map is organized as a tree of <ACRONYM
CLASS="ACRONYM"
>FSM</ACRONYM
> pages. The
bottom level <ACRONYM
CLASS="ACRONYM"
>FSM</ACRONYM
> pages store the free space available on each
heap (or index) page, using one byte to represent each such page. The upper
levels aggregate information from the lower levels.</P
><P
>Within each <ACRONYM
CLASS="ACRONYM"
>FSM</ACRONYM
> page is a binary tree, stored in an array with
one byte per node. Each leaf node represents a heap page, or a lower level
<ACRONYM
CLASS="ACRONYM"
>FSM</ACRONYM
> page. In each non-leaf node, the higher of its children's
values is stored. The maximum value in the leaf nodes is therefore stored
at the root.</P
><P
>See <TT
CLASS="FILENAME"
>src/backend/storage/freespace/README</TT
> for more details on
how the <ACRONYM
CLASS="ACRONYM"
>FSM</ACRONYM
> is structured, and how it's updated and searched.
The <A
HREF="pgfreespacemap.html"
>pg_freespacemap</A
> module
can be used to examine the information stored in free space maps.</P
></DIV
><DIV
CLASS="NAVFOOTER"
><HR
ALIGN="LEFT"
WIDTH="100%"><TABLE
SUMMARY="Footer navigation table"
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
><A
HREF="storage-toast.html"
ACCESSKEY="P"
>Prev</A
></TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
><A
HREF="index.html"
ACCESSKEY="H"
>Home</A
></TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
><A
HREF="storage-vm.html"
ACCESSKEY="N"
>Next</A
></TD
></TR
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
>TOAST</TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
><A
HREF="storage.html"
ACCESSKEY="U"
>Up</A
></TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
>Visibility Map</TD
></TR
></TABLE
></DIV
></BODY
></HTML
>